package code1201_1300.code90_100;

/**
 * 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
 *
 * 请你返回该链表所表示数字的 十进制值 。
 *
 * 输入：head = [1,0,1]
 * 输出：5
 * 解释：二进制数 (101) 转化为十进制数 (5)
 *
 * 输入：head = [0]
 * 输出：0
 *
 * 输入：head = [1]
 * 输出：1
 *
 * 输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
 * 输出：18880
 *
 * 输入：head = [0,0]
 * 输出：0
 */
public class _1290getDecimalValue {

    /**
     * 执行用时：     * 0 ms      * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 36.1 MB     * , 在所有 Java 提交中击败了     * 5.02%     * 的用户
     * @param head
     * @return
     */
    public int getDecimalValue(ListNode head) {
        ListNode node = head;
        int length = 0;
        while (node!=null){
            node = node.next;
            ++length;
        }
        int result = 0;
        for (int i = length; i > 0; i--) {
            if(head.val==1){
                result += Math.pow(2,(i-1));
            }
            head = head.next;
        }
        return result;
    }


    /**
     * 题解方法： 模拟
     * 可以不必要知道链表的长度length。
     *
     * 每读取链表的一个节点值，可以认为读到的节点值是当前二进制数的最低位；
     * 当读到下一个节点值的时候，需要将已经读到的结果乘以 2，再将新读到的节点值当作当前二进制数的最低位；
     * 如此进行下去，直到读到了链表的末尾。
     *
     * @param head
     * @return
     */
    public int getDecimalValue1(ListNode head) {
        ListNode curNode = head;
        int ans = 0;
        while (curNode != null) {
            ans = ans * 2 + curNode.val;
            curNode = curNode.next;
        }
        return ans;
    }

}
